package com.dateConstruction._06_huffmanTree;

public class HuffmanTree {
    
    // 字符集合
    private String charset;
    // 静态三叉链表结点数组
    private TriElement[] element;
    
    // 构造Huffman树，weights指定权值集合，默认字符集合是从'A'开始的weights.length个字符
    public HuffmanTree(int[] weights) {
        this.charset = "";
        // 叶子结点数
        int n = weights.length;
        for (int i = 0; i < weights.length; i++) {
            // 默认字符集合是从'A'开始的n个字符
            this.charset += (char) ('A' + i);
        }
        // n个叶子的Huffman树有2n - 1个结点
        this.element = new TriElement[2*n - 1];
        // Huffman树初始化n个叶子结点
        for (int i = 0; i < n; i++) {
            // 构造无父母的叶子结点
            this.element[i] = new TriElement(weights[i]);
        }
        // 构造n-1个2度结点
        for(int i = n; i < 2*n - 1; i++) {
            // 最小和次小权值，初值为最大整数
            int min1 = Integer.MAX_VALUE, min2 = min1;
            // 最小和次小权值结点下标
            int x1 = -1, x2 = -1;
            // 寻找两个无父母的最小权值结点下标
            for (int j = 0; j < i; j++) {
                // 第j个结点无父母
                if (this.element[j].parent == -1) {
                    // 第j个结点权值最小
                    if (this.element[j].data < min1) {
                        // min2记得次小权值
                        min2 = min1;
                        // x2记得次小权值下标
                        x2 = x1;
                        // min1记得最小权值
                        min1 = this.element[j].data;
                        // x1记得最小权值结点下标
                        x1 = j;
                    }
                    // 第j个结点权值次小
                    else if (this.element[j].data < min2) {
                        min2 = element[j].data;
                        x2 = j;
                    }
                }
            }
            // 合并两颗权值最小的子树，左孩子最小
            this.element[x1].parent = i;
            this.element[x2].parent = i;
            // 构造结点
            this.element[i] = new TriElement(min1 + min2, -1, x1, x2);
        }
        
    }
    
    public static void main(String[] args) {
        
    }

}
